package com.hc.programming.regex;

import java.util.regex.Matcher;
import java.util.regex.Pattern;

/**
 * 10.给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
 * <p>
 * '.' 匹配任意单个字符
 * '*' 匹配零个或多个前面的那一个元素
 * 所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
 * <p>
 * 示例 1：
 * <p>
 * 输入：s = "aa", p = "a"
 * 输出：false
 * 解释："a" 无法匹配 "aa" 整个字符串。
 * 示例 2:
 * <p>
 * 输入：s = "aa", p = "a*"
 * 输出：true
 * 解释：因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
 * 示例 3：
 * <p>
 * 输入：s = "ab", p = ".*"
 * 输出：true
 * 解释：".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
 *
 * @author huangchao E-mail:fengquan8866@163.com
 * @version 创建时间：2024/6/9 22:41
 */
public class 正则表达式匹配 {
    public static void main(String[] args) {
        System.out.println(isMatch("aa", "a"));
        System.out.println(isMatch("aa", "a*"));
        System.out.println(isMatch("ab", ".*"));
        System.out.println(isMatch("abc", "a***abc"));
    }

    /**
     * 方案一：基于Java正则表达式
     *
     * @param s 字符串
     * @param p 规则
     */
    public static boolean isMatch(String s, String p) {
        char[] chars = p.toCharArray();
        char pre = '$';
        StringBuilder sb = new StringBuilder();
        sb.append(pre);
        char c;
        for (int i = chars.length - 1; i >= 0; i--) {
            c = chars[i];
            sb.append(c);
            if (pre == '*' && c == '*') {
                pre = '\\';
                sb.append(pre);
            } else {
                pre = c;
            }
        }
        sb.append('^');
        Pattern pattern = Pattern.compile(sb.reverse().toString());
        Matcher matcher = pattern.matcher(s);
        return matcher.find();
    }
}
